package Tree;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * 迭代
 * 后序遍历
 */
public class PostOrderTraversalIteration {
    public static List<Integer> postOrder(TreeNode root){
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode prev = null;
        while(!stack.isEmpty() || root != null){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if(root.right == null || root.right == prev){
              res.add(root.val);
              prev = root;
              root = null;
            }else{
                stack.push(root);
                root = root.right;
            }
        }
        return res;
    }
}
